#include <bits/stdc++.h>
using namespace std;

/*
904. 水果成篮
已解答
中等
相关标签
premium lock icon
相关企业
你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。

你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：

你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。
给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。

 

示例 1：

输入：fruits = [1,2,1]
输出：3
解释：可以采摘全部 3 棵树。
示例 2：

输入：fruits = [0,1,2,2]
输出：3
解释：可以采摘 [1,2,2] 这三棵树。
如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。
示例 3：

输入：fruits = [1,2,3,2,2]
输出：4
解释：可以采摘 [2,3,2,2] 这四棵树。
如果从第一棵树开始采摘，则只能采摘 [1,2] 这两棵树。
示例 4：

输入：fruits = [3,3,3,1,2,1,1,2,3,3,4]
输出：5
解释：可以采摘 [1,2,1,1,2] 这五棵树。
 

提示：

1 <= fruits.length <= 105
0 <= fruits[i] < fruits.length
*/

// 法一
class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        // 依旧滑动窗口
        unordered_map<int, int> cnt;
        int left = 0, ans = 0;
        for (int right = 0; right < fruits.size(); right++) {
            // 进窗口
            cnt[fruits[right]]++;
            // 超过类型限制
            while (cnt.size() > 2) {
                cnt[fruits[left]]--;
                if (cnt[fruits[left]] == 0)     cnt.erase(fruits[left]);
                left++;     // 窗口左指针向右移动 窗口缩小
            }
            ans = max(ans, right - left + 1);
        }
        return ans;
    }
};

// 法二
class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        // 数组计数更高效
        int hash[100001] = {0};     // 每种水果数量
        int left = 0, kinds = 0, ans = 0;
        for (int right = 0; right < fruits.size(); right++) {
            if (hash[fruits[right]] == 0)   kinds++;

            // 也是进窗
            hash[fruits[right]]++;
            while (kinds > 2) {
                // 窗口内要减少  
                hash[fruits[left]]--;
                if (hash[fruits[left]] == 0) kinds--;
                left++;     // 滑动
            }
            ans = max(ans, right - left + 1);
        }
        return ans;
    }
};

// 法三
class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        // a 和 b 表示当前篮子中的两种水果类型
        // a 是较旧的水果类型（出现在前一种序列），b 是较新的水果类型（当前连续出现）
        int a = -1, b = -1;
        
        // cnt: 当前连续子数组的长度（采摘的总水果数）
        // result: 最终结果（最大采摘数）
        // tmp: 当前连续采摘的 b 类型水果数量
        int cnt = 0, result = 0, tmp = 0;
        
        // 遍历所有果树
        for (int i = 0; i < fruits.size(); i++) {
            int x = fruits[i];  // 当前水果类型
            
            if (x == b) {
                // 情况1：当前水果与较新类型b相同
                tmp++;    // 增加b的连续计数
                cnt++;    // 扩展当前窗口
            } else if (x == a) {
                // 情况2：当前水果与较旧类型a相同
                swap(a, b);  // 交换a和b（现在b成为最新类型）
                tmp = 1;     // 重置连续计数（当前a变b后是第一个）
                cnt++;       // 扩展当前窗口
            } else {
                // 情况3：遇到新水果类型（既不是a也不是b）
                
                // 更新最大采摘数（检查之前窗口）
                result = max(result, cnt);
                
                // 更新水果类型：
                // a = 之前连续的b类型（保留最近连续的水果）
                // b = 新的水果类型x
                a = b;
                b = x;
                
                // 新窗口长度 = 之前连续b的数量(tmp) + 当前新水果(1)
                cnt = tmp + 1;
                
                // 重置连续计数（当前新水果x是第一个）
                tmp = 1;
            }
        }
        
        // 遍历结束后更新最终结果（处理最后一组窗口）
        result = max(result, cnt);
        return result;
    }
};